Matriz de adyacencia

La matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias.

Construcción de la matriz a partir de un grafo

1. Se crea una matriz cero, cuyas columnas y filas representan los nodos del grafo.
2. Por cada arista que une a dos nodos, se suma 1 al valor que hay actualmente en la ubicación correspondiente de la matriz.
   • Si tal arista es un bucle y el grafo es no dirigido, entonces se suma 1 o 2 (dependiendo de la convención usada).
   • Si el grafo es ponderado, entonces en lugar de un 1 se suma el peso de la arista respectiva.

Finalmente, se obtiene una matriz que representa el número de aristas (relaciones) entre cada par de nodos (elementos).

Existe una matriz de adyacencia única para cada grafo (sin considerar las permutaciones de filas o columnas), y viceversa.

Ejemplos

La siguiente tabla muestra dos grafos y su respectiva matriz de adyacencia. Note que en el primer caso, como se trata de un grafo no dirigido, la matriz obtenida es simétrica:

Grafo no dirigido	Matriz de adyacencia
	${\begin{bmatrix}1&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\end{bmatrix}}$
Grafo dirigido	Matriz de adyacencia
	${\begin{bmatrix}0&1&0&0&1&0&0&0\\0&0&0&0&0&0&1&0\\0&0&0&0&0&0&0&0\\0&0&1&0&0&0&1&0\\0&0&0&0&0&0&0&0\\1&1&1&0&0&0&0&0\\0&0&0&0&0&0&0&0\\0&0&0&0&0&0&1&0\\\end{bmatrix}}$
Grafo ponderado	Matriz de adyacencia
	${\begin{bmatrix}0&4&4&0&0&0\\4&0&2&0&1&0\\4&2&0&1&0&0\\0&0&1&0&0&2\\0&1&0&0&0&4\\0&0&0&2&4&0\end{bmatrix}}$

Propiedades de la matriz de adyacencia

• Para un grafo no dirigido la matriz de adyacencia es simétrica.
• El número de caminos C_i,j(k), atravesando k aristas desde el nodo i al nodo j, viene dado por un elemento de la potencia k-ésima de la matriz de adyacencia:

$C_{i,j}(k)=[\mathbf {A} ^{k}]_{ij}$

Comparación con otras representaciones

Matriz de adyacencia

Existen otras formas de representar relaciones binarias, como por ejemplo los pares ordenados o los grafos. Cada representación tiene sus virtudes y desventajas.

En particular, la matriz de adyacencia es muy utilizada en la programación, porque su naturaleza binaria y matricial calza perfecto con la de los computadores. Sin embargo, a una persona común y corriente se le hará mucho más sencillo comprender una relación descrita mediante grafos, que mediante matrices de adyacencia.

Otra representación matricial para las relaciones binarias es la matriz de incidencia.

Aplicaciones

La relación entre un grafo y el vector y valor propio de su correspondiente matriz de adyacencia se estudian en la teoría espectral de grafos.

En sociometría, a las matrices de adyacencia se les conoce como sociomatrices, y se utilizan como una forma de notación alternativa y complementaria a los sociogramas. Son además una de las formas de denotar redes sociales para el análisis de redes sociales.​

Véase también

• Matriz de incidencia
• Matriz laplaciana

Bibliografía

• Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN 978-84-7476-631-8. OCLC 871814053. 

• Datos: Q727035
• Multimedia: Adjacency matrices of graphs / Q727035